Description

Given an undirected graph with $N$ vertices and $M$ edges, where each edge has weight $1$.

You are also given $K$ ordered triples $(A,B,C)$, meaning that after moving from $A$ to $B$, you are not allowed to move to $C$. Note that the triples are ordered; for example, it is allowed to go from $B$ to $A$ and then to $C$.

Under the constraints given by the $K$ triples, find the shortest path from node $1$ to node $N$, and output any valid path. A Check will verify your output.

Input Format

The first line contains three integers $N$, $M$, $K$, as described above.

Each of the next $M$ lines contains two integers $A$, $B$, indicating there is an edge between $A$ and $B$.

Each of the next $K$ lines contains three integers $(A,B,C)$ describing one triple.

Output Format

Output consists of two lines. The first line contains a single integer $S$, the length of the shortest path.

The second line contains $S+1$ integers, the sequence of nodes visited from $1$ to $N$.

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4

4 
1 3 2 3 4 

Hint

For 40% of the testdata, $N \le 10$, $M \le 20$, $K \le 5$.

For 100% of the testdata, $N \le 3000$, $M \le 20000$, $K \le 100000$.

Translated by ChatGPT 5