{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Consider a directed graph **G** consisting of **n** nodes and **m** directed edges. Nodes are numbered from **1** to **n** and edges are numbered from **1** to **m**. Let\u0027s select some node **r** as the starting one and find all nodes that are reachable from **r** by moving along edges (denote this set as `C[0]`). Define **C**(**e**) as the set of nodes which are reachable from **r** using any edges except the one with number **e**. Edge **e** is called _redundant_ if **C**(**e**) is equal to `C[0]`.\r\n\r\nYou are given the graph **G** and the starting node **r**. Your goal is to find all _redundant_ edges.\r\n\r\n#### Input\r\nThe first line contains three integers **n**, **m** and **r** (**1** ≤ **n** ≤ **100000**, **1** ≤ **m** ≤ **200000**, **1** ≤ **r** ≤ **n**): the number of nodes, the number of edges and the starting node, respectively. Next **m** lines describe the edges of the graph: **i**-th of them contains two integers `a[i]` and `b[i]` (**1** ≤ `a[i]`, `b[i]` ≤ **n**) which introduce a directed edge from node `a[i]` to node `b[i]`. It is guaranteed that there are no loops, and for any two nodes **u** and **v**, there is at most one edge from **u** to **v**.\r\n\r\n#### Output\r\nOn the first line, print the number of redundant edges. On the second line, print the numbers of all redundant edges in any order. Edges are numbered starting from **1** according to their order in the input."}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 1\n1 2\n2 3\n3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 6 2\n2 1\n2 3\n3 1\n3 4\n1 4\n4 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n1 3 4 5 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}