만드는 중입니다

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

자동 프로그램 분석기

면접 대비

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

요약
각 테스트 케이스마다 인덱스가 최대 10억인 변수들의 같음과 다름 제약을 모두 동시에 만족하는 값 배정이 있는지 판별합니다.
난이도

보통10점 중 4점

유형
유니온 파인드, 해시맵
정답자
아직 제출이 없습니다

문제

변수 x1,x2,x3,…x_1, x_2, x_3, \dots가 주어진다. xi=xjx_i = x_j 또는 xi≠xjx_i \ne x_j 꼴의 제약 조건이 nn개 주어진다. 모든 제약 조건을 동시에 만족하도록 변수에 값을 배정할 수 있는지 판단한다. 예를 들어 제약 조건이 x1=x2x_1 = x_2, x2=x3x_2 = x_3, x3=x4x_3 = x_4, x1≠x4x_1 \ne x_4이면, 이 조건들을 모두 만족시킬 수 없다.

입력

첫 줄에 독립적인 테스트 케이스의 개수 tt가 주어진다. 각 테스트 케이스의 첫 줄에는 제약 조건의 개수 nn이 주어진다. 이어서 nn개의 줄에 제약 조건 하나를 나타내는 정수 ii, jj, ee가 주어진다. e=1e = 1이면 xi=xjx_i = x_j, e=0e = 0이면 xi≠xjx_i \ne x_j인 제약이다.

출력

tt줄에 걸쳐 출력한다. kk번째 줄에는 kk번째 테스트 케이스의 제약 조건을 모두 만족시킬 수 있으면 YES, 그렇지 않으면 NO를 출력한다.

제한

  • 1≤n≤100 0001 \le n \le 100\,000\n- 1≤i,j≤1 000 000 0001 \le i, j \le 1\,000\,000\,000\n- 1≤t≤101 \le t \le 10\n- e∈{0,1}e \in \{0,1\}

예제2

  1. 예제 1

    입력
    2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
    예상 출력
    NO
YES

  2. 예제 2

    입력
    2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
    예상 출력
    YES
NO