Hide

Fetch the Stuff

/problems/rupc19.fetchthestuff/file/statement/en/img-0001.jpg
A locked door.
It is getting late, and after a long day of studying, Hannes is ready to head home. But now he realizes that he forgot his backpack in one of the classrooms, and his jacket is still in the student lounge. This wouldn’t be such a big deal if it were not for the fact that some of the doors in the university building will automatically become locked when it is late in the evening. While Hannes will be able to exit through a locked door, the door will immediately slam shut behind him, at which point he will not be able to go back through.

Hannes now wonders if he will be able to fetch all his stuff, and then exit the building. Given a description of the $n$ parts of the university, the $m$ open and locked doors that separate these parts, as well as the $k$ different parts that Hannes needs to visit to fetch his stuff, can you help him determine if he can fetch all his stuff and then exit the building?

Hannes’ current location is in part $1$, and outside the building is represented as part $n$.

Input

The input consists of:

  • One line with three integers $n$, $m$ and $k$ ($3 \le n \le 5\, 000$, $1 \le m \le 10^5$, $1 \le k \le 30$), the number of parts of the building, open and locked doors that separate them, and parts that Hannes needs to visit in order to fetch his stuff.

  • One line with $k$ distinct integers $p_1,\ldots ,p_ k$ ($1 < p_ i < n$), the parts that Hannes needs to visit in order to fetch his stuff.

  • $m$ lines, describing the doors.

    The $i$th such line starts with two integers $q_ i$ and $r_ i$ ($1 \le q_ i, r_ i \le n$, $q_ i \neq r_ i$), indicating that there is a door that separates parts $q_ i$ and $r_ i$ of the building.

    The remainder of the line contains a string $s_ i$, either “open” or “locked”, indicating whether this door is open or locked. If the door is locked, Hannes can only use the door to go from part $q_ i$ of the building to part $r_ i$ of the building. If the door is open, Hannes can use the door to travel between parts $q_ i$ and $r_ i$ as he wishes.

Output

If it is possible for Hannes to pick up all his stuff and then exit the building, output a sequence $t_1,\ldots ,t_ l$ of parts that Hannes can visit, in the order that he should visit them, so that he can pick up all his stuff. It must hold that:

  • He starts at his current location, i.e. $t_1 = 1$.

  • He ends outside the building, i.e. $t_ l = n$.

  • For any two consecutive parts $t_ i$ and $t_{i+1}$ that he visits, there must exist a door that allows Hannes to travel directly from part $t_ i$ of the building to part $t_{i+1}$ of the building.

  • Hannes must visit all the parts he needs to visit in order to fetch all his stuff, i.e. for each $i~ \in ~ \{ 1,\ldots ,k\} $ there must exist at least one $j\in \{ 1,\ldots ,l\} $ such that $p_ i = t_ j$.

It is guaranteed that if there exists a valid sequence, there exists a valid sequence of length at most $2\cdot 10^5$. Furthermore, your sequence must satisfy $l \le 2\cdot 10^5$. If there are multiple valid sequences, you may output any of them.

If it is not possible for Hannes to pick up all his stuff and then exit the building, output “impossible”.

Sample Input 1 Sample Output 1
4 4 2
2 3
1 3 locked
3 4 locked
1 2 locked
2 4 open
1
3
4
2
4
Sample Input 2 Sample Output 2
5 7 2
3 4
1 2 locked
1 3 open
2 3 locked
1 5 locked
2 4 locked
5 4 locked
5 4 open
1
3
1
5
4
5
Sample Input 3 Sample Output 3
5 5 2
2 4
1 2 locked
1 3 locked
2 3 locked
1 5 locked
5 4 open
impossible
CPU Time limit 3 seconds
Memory limit 1024 MB
Authors
Arnar Bjarni Arnarson, Bjarki Ágúst Guðmundsson, and Unnar Freyr Erlendsson
Source Reykjavík University Spring Contest 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in