Hula's Cardgame
Time limit2sMemory limit512 MB
Given tables whose three cards point to tables at or above their own number, decide for each E whether Geunsu can reach table E while Seunghyeong deletes one card per move.
- Level
Hard8 of 10
- Topics
- Game theory, Graph, DFS
- Solved
- No attempts yet
Problem
Geunsu and Seunghyeong want to play Hula's Cardgame at K512. K512 has tables, numbered from to . Each table has 3 cards, and each card on table holds an integer from to , inclusive.
Geunsu and Seunghyeong are at table now. Table has a Umaru Doma doll that Geunsu likes, so Geunsu wants to go to table . Seunghyeong dislikes this and does not want to go to table . They repeat the following steps until the game ends.
- If the current table is table , Geunsu wins.
- If the current table is not table , Seunghyeong removes one of the 3 cards on the current table.
- Geunsu picks one of the 2 remaining cards on the current table. They move to the table whose number is the integer on that card. If the integer on the chosen card equals the current table number, meaning they revisit a table they have already visited, Seunghyeong wins.
Assume both play optimally. Geunsu wants to know whether he can win. Solve this for every with .
Input
The first line contains the number of tables . ()
From the second line to the th line, the integers , , on the 3 cards of each table are given, separated by spaces. The th line gives the 3 integers on the cards of table . ()
Output
On the th line, print Yes if Geunsu can win when , and No if he loses.