Promotions

The management of Fair Inc. decided to promote its best employees and capped the number of promotions to the interval $[A, B]$. The directors compared the employees' results, and their evaluation produced a consistent precedence relation among employees that every promotion round has to respect. For every pair of employees $x$ and $y$, if $x$ outperformed $y$, then $y$ may be promoted only if $x$ is promoted.

To learn whether the data collected so far is enough to guarantee fairness, the executive chairman asks two questions.

• How many employees are certainly promoted at each endpoint of the interval, that is, when the number of promotions is $A$ and when it is $B$?
• How many employees have no possibility of being promoted, even when the number of promotions is $B$?

Look at the example in the figure. There are seven employees and eight precedence rules. An arrow from employee $x$ to employee $y$ means that $x$ outperformed $y$. The number of promotions is capped to the interval $[3, 4]$.

• With three promotions the promoted set is either Anne, Bob and Greg, or Anne, Eve and Greg. Two employees (Anne and Greg) are therefore certainly promoted. The current data does not say whether Bob and Eve get a promotion.
• With four promotions the only promoted set is Anne, Bob, Eve and Greg. So four employees (Anne, Bob, Eve and Greg) are certainly promoted, and three employees (Cora, Dan and Fred) have no possibility of being promoted.

Write a program that, given the interval for the number of promotions, the set of employees and the precedence relation among them, computes the number of employees that are certainly promoted at each endpoint of the interval, and the number of employees that have no possibility of being promoted.

The precedence relation is consistent. If employee $x$ outperformed employee $y$, then $y$ did not outperform $x$, directly or indirectly.

The first line has four space separated integers $A$, $B$, $E$ and $P$. $A$ and $B$ are the endpoints of the interval, $E$ is the number of employees, and $P$ is the number of precedence rules. Employees are identified by the integers $0$ to $E - 1$. Each of the next $P$ lines holds two distinct space separated integers $x$ and $y$, meaning that employee $x$ outperformed employee $y$.

Constraints

• $1 \le A < B < E$ (interval endpoints)
• $2 \le E \le 5000$ (number of employees)
• $1 \le P \le 20000$ (number of precedence rules)

Print three lines.

The first line holds the number of employees that are certainly promoted when the number of promotions is $A$. The second line holds the number of employees that are certainly promoted when the number of promotions is $B$. The third line holds the number of employees that have no possibility of being promoted, even when the number of promotions is $B$.