This is a problem I was given back when I'm training for APIO Vietnam team selection.

"There are *n* ( *n* ≤ 600) factory that is planned to be built on a line, number from 1 to *n*. There are *m* ( *m* ≤ 100000) restriction, each restriction has form *uv*, meaning that if both factory *u* and *v* is built, *x* _{ u} + 1 = *x* _{ v}. There are another *p* ( *p* ≤ 100000) restriction, each restriction has form *uv*, meaning that if both factory *u* and *v* is built, *x* _{ u} ≤ *x* _{ v}. ( *x* _{ i} mean coordinate of factory *i*, if it's going to be built)

Your task is to choose a set of factories to build, and pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of built factories is maximum."

I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.