Splitting into Two Classes

Jongmin works as the homeroom teacher of class 3 in the fifth grade at CTP Elementary School. Recently many fifth graders have transferred to CTP Elementary School, so as a countermeasure the school decided to split Jongmin's class 3 into two sections.

Jongmin had long suffered because of the students in his class. The fifth grade class 3 students often refuse to listen during class and play with each other instead, so splitting class 3 into two sections was very welcome news to Jongmin.

Jongmin wants to reduce his suffering by placing every pair of students who are close friends in different sections. But since such a placement is sometimes impossible, he came up with a scheme for those cases. He spreads a rumor that two students who are close friends are badmouthing each other, making the two friends fall out! When two students who are close friends fall out, they are no longer close friends.

In this way Jongmin made a list of close friend pairs to make fall out. Of course, he does not want students to split into factions and fight after he makes close friend pairs fall out left and right, so he made sure that even if every close friend pair in the list falls out, the students do not split into factions. Not splitting into factions means that the graph whose edges connect every pair of students who are close friends is connected.

Jongmin makes the close friend pairs in the list fall out in the order written, and then wants to find peace by placing the students so that no two students who are close friends end up in the same section. But having some conscience left as a teacher, Jongmin wants to make as few close friend pairs fall out as possible. What is the minimum number of close friend pairs he must make fall out so that the students can be split so that no section contains two students who are close friends?

The first line gives (N), (M), and (K), separated by spaces.

• (N) is the number of students in fifth grade class 3.
• (M) is the number of close friend pairs in fifth grade class 3.
• (K) is the number of close friend pairs in the list Jongmin will make fall out.

Each of the next (M) lines gives (u_i) and (v_i), separated by a space, describing the (i)-th close friend pair. This means student (u_i) and student (v_i) are close friends. No pair is repeated.

Each of the (K) lines starting from line (M)+2 gives (R_i). This means the (i)-th close friend pair to make fall out is the (R_i)-th close friend pair. All given (R_i) are guaranteed to be distinct.

On the first line, print the minimum number of close friend pairs that must be made to fall out.

On the second line, print the numbers of students in the two sections in ascending order.

If the students cannot be split into two sections even after every close friend pair in the list is made to fall out, print "-1" on the first line instead.

• 2 ≤ (N) ≤ 105
• (N) - 1 ≤ (M) ≤ min((\frac{N(N - 1)}{2}), 2 × 105)
• 0 ≤ (K) ≤ (M) - (N) + 1
• 1 ≤ (u), (v) ≤ (N), (u \ne v)
• 1 ≤ (R_i) ≤ (M)

The initial close friend relations of sample 1 are shown in the following graph.

Jongmin plans to make the 5th, 3rd, and 7th close friend pairs fall out, in that order. If he makes the 5th and 3rd pairs fall out, he can place students 1 and 4 in one section and students 2, 3, and 5 in the other, so that no section contains a close friend pair.

It is impossible to satisfy the conditions of the problem while making fewer pairs fall out.