레인보우 스패닝 트리

무향 그래프 $G$가 주어진다. 그래프는 $N$개의 정점과 $M$개의 간선으로 이루어져 있으며, 정점에는 $1,2,\cdots,N$의 번호가 붙어 있다.

각 간선은 색 $1,2,\cdots,7$ 중 하나로 칠할 수 있다. 단, 모든 간선을 모든 색으로 칠할 수 있는 것은 아니다. $i$번 간선에 대해 $p_{i,j}=1$이면 $i$번 간선을 $j$번 색으로 칠할 수 있고, $p_{i,j}=0$이면 $i$번 간선을 $j$번 색으로 칠할 수 없다.

$Q$개의 질의가 주어진다. 각 질의는 일곱 정수 $a_1,a_2,\cdots,a_7$로 이루어져 있다.

각 질의마다, 다음 조건을 모두 만족하는 스패닝 트리와 색 배정이 존재하는지 판단하여라.

• 그래프에서 정확히 $N-1$개의 간선을 골라 모든 정점을 연결하는 트리를 만든다.
• 고른 각 간선에는 그 간선에 허용된 색 중 하나를 칠한다.
• 모든 $j$ ($1 \leq j \leq 7$)에 대해, $j$번 색으로 칠해진 간선의 개수가 정확히 $a_j$개이다.

가능한 경우 Yes, 불가능한 경우 No를 출력하여라.

그래프가 연결되어 있음은 보장되지 않는다.

입력은 다음과 같은 형식으로 주어진다.

$N\ M$ $u_1\ v_1\ p_{1,1}\ p_{1,2}\ \cdots\ p_{1,7}$ $u_2\ v_2\ p_{2,1}\ p_{2,2}\ \cdots\ p_{2,7}$ $\vdots$ $u_M\ v_M\ p_{M,1}\ p_{M,2}\ \cdots\ p_{M,7}$ $Q$ $a_{1,1}\ a_{1,2}\ \cdots\ a_{1,7}$ $a_{2,1}\ a_{2,2}\ \cdots\ a_{2,7}$ $\vdots$ $a_{Q,1}\ a_{Q,2}\ \cdots\ a_{Q,7}$

각 질의마다 한 줄에 하나씩 답을 출력한다.

$q$번 질의를 만족하는 스패닝 트리와 색 배정이 존재하면 Yes를 출력한다. 존재하지 않으면 No를 출력한다.

• $2 \leq N \leq 100\ 000$.
• $1 \leq M \leq 100\ 000$.
• $1 \leq Q \leq 100\ 000$.
• $1 \leq u_i, v_i \leq N$ ($1 \leq i \leq M$).
• $u_i \neq v_i$ ($1 \leq i \leq M$).
• 같은 두 정점을 잇는 간선이 여러 개 있을 수 있다.
• $p_{i,j} \in \{0,1\}$ ($1 \leq i \leq M$, $1 \leq j \leq 7$).
• 각 $i$번 간선에 대해 $p_{i,1}+p_{i,2}+\cdots+p_{i,7} \geq 1$이다 ($1 \leq i \leq M$).
• $0 \leq a_{q,j} \leq N-1$ ($1 \leq q \leq Q$, $1 \leq j \leq 7$).