Cut Vertices and Bridges

In graph theory, a cut vertex and a bridge are defined as follows.

• Cut vertex: if deleting a vertex splits the connected component that contained it into two or more components, that vertex is a cut vertex.
• Bridge: if deleting an edge splits the connected component that contained it into two or more components, that edge is a bridge.

This problem asks for cut vertices and bridges of a tree. A tree is a graph with no cycle in which every vertex is connected.

Given a tree and a list of queries, answer each query.

Input comes from standard input. The first line has the number of vertices $N$ of the tree. ($2 \le N \le 100000$) The vertices are numbered from 1 to $N$. Each of the next $N-1$ lines has an edge $a$ and $b$, meaning vertex $a$ and vertex $b$ are connected. The given graph is always a tree. ($1 \le a, b \le N$)

The next line has the number of queries $q$. ($1 \le q \le 100000$) Each of the next $q$ lines has a query $t$ and $k$. ($1 \le t \le 2$) If $t$ is 1, the query asks whether vertex $k$ is a cut vertex. If $t$ is 2, the query asks whether the $k$-th edge of the input is a bridge. When $t$ is 1, $1 \le k \le N$. When $t$ is 2, $1 \le k \le N-1$.

Print to standard output. For the $q$ queries, print one answer per line. Print yes if the queried vertex is a cut vertex or the queried edge is a bridge, and no otherwise.