23594번 - Vasya's graph 다국어

문제

Vasya has got a graph. The graph has $N$ nodes, but it's got no eges yet. Vasya cares a lot about the future graph structure: he knows $K$ pairs of nodes {$u_j,ドル $v_j$}, such that if there is a path between these nodes in the graph, the irredeemable will happen to the graph. Vasya must prevent it at all costs.

Vasya has made a list of $M$ unoriented edges. Vasya will examine the edges in the preset order and he will surely put them into the graph, if possible. If adding another edge will cause the irredeemable, Vasya will simply discard such an edge. Your task is to find out which edges are good for the graph and which ones must end up in the trash.

입력

The first line of the input file contains three integers $N,ドル $K$ and $M$ (1ドル \leq N \leq 10^5,ドル 0ドル \leq K, M \leq 10^5$).

It is followed by $K$ lines, with the $i$-th line containing two integers $u_i$ and $v_i$ --- the numbers of conflicting nodes, which should not have any edges between them (1ドル \leq u_i < v_i \leq N$). The conflicting node pairs are unique.

Next come $M$ lines with the $i$-th line containing two integers $\tilde u_i$ and $\tilde v_i$ --- the numbers of nodes of the edge which can be added to the graph (1ドル \leq \tilde u_i < \tilde v_i \leq N$). These edges are provided in the order of examination. Edges in the list are unique.

출력

The first line of the output file must contain the number of edges that Vasya can accomodate into the graph. The second line must contain space-separated numbers of edges in the ascending order.

제한

힌트