J. Indiana Jiang and the Temple of Kukulkan
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the remote corners of Mexico, hidden among the mystical ruins of the Temple of Kukulkan, lie the most well-guarded secrets of the ancient Mayan programmers. Legend has it that the transcendent knowledge of ancient algorithms is protected by a mysterious Encoded Chamber, access to which is safeguarded by a clever enigma.

The entrance to the Encoded Chamber does not resemble any ordinary door. A sequence of sacred symbols, initially representing the sun, adorns the facade of the passage. In front of it, a set of elaborately carved levers is arranged on a stone panel. Every time a lever is pulled, exactly two of the sacred symbols mysteriously change form: a sun transforms into a moon, and a moon transforms into a sun.

The guardian of this chamber is Indiana Jiang, a renowned archaeologist who, after years of tireless research, has discovered a sequence of symbols that, once obtained, will reveal the path to the ancestral knowledge. Exhausted from his investigations, Jiang requests your help to rescue the Mayan secrets before they fall into the wrong hands. Find a set of levers that, when pulled, will open the door to the Encoded Chamber.

Input

The first line of the input contains two integers $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$), representing the number of levers, and $$$m$$$ ($$$2 \leq m \leq 5 \cdot 10^5$$$), representing the number of symbols on the passage.

Each of the following $$$n$$$ lines contains two integers $$$s_{i, 1}$$$ and $$$s_{i, 2}$$$ ($$$1 \leq s_{1, i}, s_{2, i} \leq m$$$, $$$s_{1, i} \neq s_{2, i}$$$), which are the symbols connected to lever $$$i$$$.

The last line contains a sequence of $$$m$$$ digits representing the symbol sequence that opens the door to the Encoded Chamber. The digit 0 represents the sun, and the digit 1 represents the moon.

Output

Print -1 if there is no solution. If there is a solution, print the number of levers to be pulled and a list of these levers (without repetition). If there is more than one solution, you can print any one of them.

Example
Input
2 3
1 2
2 3
1 0 1
Output
2
1 2