Migrated from Lutece 148 H-edges

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A simple graph is given with $N$ nodes and $M$ edges, each edge's length is $1$. Given you the node $S$, for each node $V$, you should calculate the odd and even shortest distance from the node $S$ ($V\neq S$). (that is the shortest distance with length of odd and even, the route isn't necessarily a simple route).

We define the odd shortest distance to be odd($V$), and the even shortest distance to be even($V$). And we call the maximal one of them to be max($V$). We say a route from $S$ to $V$ whose length is max($V$) is a beautiful route (not necessarily only one), and every beautiful route's last edge is defined to be the T-edge. If there is no odd shortest route or no even shortest route for node $V$, then there are no beautiful routes ended by node $V$.For those edges which is not a T-edge, we say them H-edges.

Now, can you help us to find out all the H-edges.

Input

In the first line, you will get a number $T$ denotes the number of test cases.

For each test case,

In the first line, you will get $2$ number $N$ ($1\leq N\leq 100000$) and $M$ ($1\leq M\leq 1000000$), denote the number of nodes and edges.

Then $M$ lines comes,

In the $i_{th}$ line, $2$ numbers $A$ and $B$ are given, indicate there is a road between node $A$ and node $B$,($0\leq A,B < N$) the symbol of this road is $i$.

Then a number $S$ is given as described above.

Output

For each test case, you should output $2$ lines.

The first line contain a number $K$ denotes the number of H-edges.

In the second line, you should output $K$ numbers denote the symbol of all the H-edges in ascending order.

Samples

1
8 8
0 1
1 2
2 3
0 4
2 5
4 5
5 6
6 7
0

2
1 4

Resources

Sichuan State Programming Contest 2008