만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

Hula's Cardgame

시간 제한2초메모리 제한512 MB

요약
각 테이블의 카드 3장은 같거나 더 큰 번호의 테이블을 가리킵니다. Seunghyeong이 매번 카드 한 장을 지울 때 Geunsu가 각 E에 도달할 수 있는지 판정합니다.
난이도

어려움10점 중 8점

유형
게임 이론, 그래프, DFS
정답자
아직 제출이 없습니다

문제

근수와 승형이는 K512에서 Hula's Cardgame을 즐기려고 한다. K512에는 NN개의 테이블이 있고, 1번부터 NN번까지 차례대로 번호가 붙어 있다. 각 테이블 위에는 카드 3장이 놓여 있으며, ii번 테이블의 카드 3장에는 각각 ii 이상 NN 이하인 정수가 적혀 있다.

근수와 승형이는 지금 1번 테이블에 있다. EE번 테이블에는 근수가 좋아하는 도마 우마루 인형이 있어서, 근수는 EE번 테이블로 가고 싶어 한다. 승형이는 근수가 못마땅해서 EE번 테이블로 가는 것을 원하지 않는다. 두 사람은 게임이 끝날 때까지 다음 행동을 반복한다.

  1. 현재 테이블이 EE번 테이블이라면 근수가 게임에서 이긴다.
  2. 현재 테이블이 EE번 테이블이 아니라면 승형이가 현재 테이블의 카드 3장 중 한 장을 제거한다.
  3. 근수가 현재 테이블에 남은 카드 2장 중 한 장을 고른다. 두 사람은 그 카드에 적힌 수의 번호를 가진 테이블로 이동한다. 고른 카드에 적힌 수가 현재 테이블 번호와 같다면, 즉 이미 방문한 테이블을 다시 방문하게 되면 승형이가 게임에서 이긴다.

두 사람이 항상 최선의 전략으로 게임한다고 할 때, 근수가 이길 수 있는지 구하라. 모든 EE (1≤E≤N1 \le E \le N)에 대해 풀어라.

입력

첫 번째 줄에 테이블의 개수 NN이 주어진다. (1≤N≤2×1051 \le N \le 2\times10^5)

두 번째 줄부터 N+1N+1번째 줄까지 각 테이블의 카드 3장에 적힌 정수 aia_i, bib_i, cic_i가 공백으로 구분되어 주어진다. jj번째 줄에는 j−1j-1번 테이블의 카드 3장에 적힌 정수 3개가 주어진다. (i≤ai,bi,ci≤Ni \le a_i, b_i, c_i \le N)

출력

ii번째 줄에 E=iE = i일 때 근수가 이길 수 있으면 Yes를, 지면 No를 출력한다.

예제2

  1. 예제 1

    입력
    6
    2 3 4
    2 2 3
    4 5 6
    4 5 6
    5 6 6
    6 6 6
    
    예상 출력
    Yes
    No
    No
    No
    No
    Yes
    
  2. 예제 2

    입력
    6
    2 3 4
    2 3 3
    4 5 6
    5 5 5
    6 6 6
    6 6 6
    
    예상 출력
    Yes
    No
    Yes
    No
    Yes
    Yes