아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Easy Compare-and-Set

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

요약
초기값과 함께 성공 또는 실패가 요구되는 CAS(a,b) 연산들이 주어질 때, 모든 요구를 만족하는 실행 순서를 찾거나 불가능함을 판정한다.
난이도

보통10점 중 7점

유형
그래프, 위상 정렬, 그리디, 구현
정답자
아직 제출이 없습니다

문제

Let us define "Compare-and-Set" operation for a global variable vv. The operation checks if the variable is equal to aa. If that's true, the variable value changes to bb and the operation succeeds. Otherwise, the variable doesn't change and the operation fails. Let us denote the operation as CAS⁡(a,b)\operatorname{CAS}(a,b).

Imagine that you are given a list of such operations CAS⁡(a_1,b_1),…,CAS⁡(a_n,b_n)\operatorname{CAS}(a\_1,b\_1), \dots, \operatorname{CAS}(a\_n,b\_n). Also, you are given an initial value for the variable, cc, and a list of wishes w_1,…w_nw\_1, \dots w\_n, where w_iw\_i tells whether the operation CAS⁡(a_i,b_i)\operatorname{CAS}(a\_i,b\_i) should be successful. Your task is to determine the order of operations execution so that all the wishes are satisfied.

입력

The first line contains two integers nn and cc (1≤n≤1051 \le n \le 10^5; 1≤c≤1091 \le c \le 10^9) --- the number of operations and the initial value of the variable.

Each of the next nn lines contains three integers a_i,b_i,w_ia\_i, b\_i, w\_i (1≤a_i,b_i≤1091 \le a\_i, b\_i \le 10^9; 0≤w_i≤10 \le w\_i \le 1), denoting CAS⁡(a_i,b_i)\operatorname{CAS}(a\_i, b\_i) operation that you wish to be successful if w_i=1w\_i = 1 and unsuccessful if w_i=0w\_i = 0. The operations are numbered from 11 to nn in order of input.

출력

If no correct order of operations exists, output a single word "No".

Otherwise, output a word "Yes" followed by nn distinct integers p_1,p_2,…p_np\_1, p\_2, \ldots p\_n (1≤p_i≤n1 \le p\_i \le n), meaning that operation p_1p\_1 should be executed first, then operation p_2p\_2, and so on. If there are several possible orders, output any of them.

예제2

  1. 예제 1

    입력
    4 1
    1 2 0
    1 2 1
    2 3 1
    3 4 0
    
    예상 출력
    Yes
    4 2 1 3
    
  2. 예제 2

    입력
    3 1
    1 2 1
    1 2 1
    1 2 0
    
    예상 출력
    No