Kiara does not know the real graph $cal(G)$ governing the flight of these birds but, in her previous field study, Kiara has collected data from the journey of many birds. Using this, she has devised a graph $cal(P)$ explaining how they move. Kiara has spent so much time watching them that she is confident that if a bird can fly directly from $a$ to $b$, then she has witnessed at least one such occurrence. However, it is possible that a bird flew from $a$ to $b$ to $c$ but she only witnessed the stops $a$ and $c$ and then added $(a, c)$ to $cal(P)$. It is also possible that a bird flew from $a$ to $b$ to $c$ to $d$ and she only witnessed $a$ and $d$, and added $(a, d)$ to $cal(P)$ , etc. To sum up, she knows that $cal(P)$ contains all the edges of $cal(G)$ and that $cal(P)$ might contain some other edges $(a, b)$ for which there is a path from $a$ to $b$ in $cal(G)$ (note that $cal(P)$ might not contain all such edges).
For her next field study, Kiara has decided to install her base next to a given tree $T$. To be warned of the arrival of birds on $T$, she would also like to install detectors on the trees where the birds can come from (i.e. the trees $T '$ such that there is an edge ( $T ', T$) in $cal(G)$ ). As detectors are not cheap, she only wants to install detectors on the trees $T '$ for which she is sure that $(T ', T)$ belongs to $cal(G)$.
Kiara is sure that an edge $(a, b)$ belongs to $cal(G)$ when $(a, b)$ is an edge of $cal(P)$ and all the paths in $cal(P)$ starting from $a$ and ending in $b$ use the edge $(a, b)$. Kiara asks you to compute the set $S (T)$ of trees $T '$ for which she is sure that $(T ', T)$ is an edge of $cal(G)$.
The input describes the graph $cal(P)$. The first line contains three space-separated integers $N$, $M$, and $T$: $N$ is the number of nodes of $cal(P)$, $M$ is the number of edges of $P$ and $T$ is the node corresponding to the tree on which Kiara will install her base.
The next $M$ lines describe the edges of the graph $cal(P)$. Each contains two space-separated integers $a$ and $b$ ($0 <= a$, $b < N$ and $a != b$) stating that $(a, b) in cal(P)$ . It is guaranteed that the same pair $(a, b)$ will not appear twice.
*Limits*
Your output should describe the set $S (T)$. The first line should contain an integer $L$, which is the number of nodes in $S (T)$, followed by $L$ lines, each containing a different element of $S (T)$. The elements of $S (T)$ should be printed in increasing order, with one element per line.
*Sample Explanation 1*
The graph corresponding to this example is depicted below. The node 1 belongs to $S (2)$ because the (only) path from 1 to 2 uses (1, 2). The node 0 does not belong to $S (2)$ because the path $0 arrow.r 1 arrow.r 2$ does not use the edge (0, 2).
*Sample Explanation 2*
The graph corresponding to this example is depicted below. For the same reason as in Sample 1, the node 0 does not belong to $S (2)$ while 1 does. The nodes 3 and 5 do not belong to $S (2)$ because we do not have edges (3, 2) or (5, 2). Finally 4 belongs to $S (2)$ because all paths from 4 to 2 use the edge (4, 2).
## Input
The input describes the graph $cal(P)$. The first line contains three space-separated integers $N$, $M$, and $T$: $N$ is the number of nodes of $cal(P)$, $M$ is the number of edges of $P$ and $T$ is the node corresponding to the tree on which Kiara will install her base.The next $M$ lines describe the edges of the graph $cal(P)$. Each contains two space-separated integers $a$ and $b$ ($0 <= a$, $b < N$ and $a != b$) stating that $(a, b) in cal(P)$ . It is guaranteed that the same pair $(a, b)$ will not appear twice.*Limits* $1 <= N, M <= 100000$; $0 <= T < N$.
## Output
Your output should describe the set $S (T)$. The first line should contain an integer $L$, which is the number of nodes in $S (T)$, followed by $L$ lines, each containing a different element of $S (T)$. The elements of $S (T)$ should be printed in increasing order, with one element per line.
[samples]
## Note
*Sample Explanation 1*The graph corresponding to this example is depicted below. The node 1 belongs to $S (2)$ because the (only) path from 1 to 2 uses (1, 2). The node 0 does not belong to $S (2)$ because the path $0 arrow.r 1 arrow.r 2$ does not use the edge (0, 2). *Sample Explanation 2*The graph corresponding to this example is depicted below. For the same reason as in Sample 1, the node 0 does not belong to $S (2)$ while 1 does. The nodes 3 and 5 do not belong to $S (2)$ because we do not have edges (3, 2) or (5, 2). Finally 4 belongs to $S (2)$ because all paths from 4 to 2 use the edge (4, 2).
**Definitions**
Let $ j, g, c, p \in \mathbb{Z}^+ $ denote the grid dimensions, required separation distance, and number of shoe pairs, respectively.
**Constraints**
1. $ 1 \le t \le 10^5 $
2. For each test case:
- $ 1 \le j, g, c, p \le 10^{18} $
**Objective**
Determine whether it is possible to place $ 2p $ distinct shoes on a $ j \times g $ grid such that:
- Each shoe is paired with exactly one other shoe (forming $ p $ disjoint pairs).
- For each pair, the two shoes are separated by exactly $ c $ cells in one of the four cardinal directions (up, down, left, right).
- No cell contains more than one shoe.
Equivalently:
Is there a set of $ p $ disjoint pairs of cells $ \{(x_1, y_1), (x_2, y_2)\} $ in the grid $ \{1, \dots, j\} \times \{1, \dots, g\} $, such that for each pair, $ |x_1 - x_2| + |y_1 - y_2| = c $ and $ \min(|x_1 - x_2|, |y_1 - y_2|) = 0 $?
That is, each pair lies on the same row or same column, with Manhattan distance exactly $ c $.