Tropical Garden

The botanist Chulsoo visits a huge tropical garden together with several school classes. The garden has $N$ ponds, numbered $0$ through $N-1$, and $M$ walkways, numbered $0$ through $M-1$. Each walkway connects two distinct ponds and can be traversed in both directions. Every pond has at least one walkway attached to it, and between any two ponds there is at most one walkway.

The walkways are numbered in decreasing order of beauty: for every $i\ (0 \le i < M-1)$, walkway $i$ is more beautiful than walkway $i+1$. Because Chulsoo is a botanist, no two walkways are ever equally beautiful.

Chulsoo and the students move according to the following rule. At the current pond they always take the most beautiful attached walkway. However, if that walkway is exactly the one they used on the previous move, they take the second most beautiful walkway instead. The only exception is when the current pond has just one attached walkway: there is no second choice, so they reuse the walkway they just arrived on. (At the start no walkway has been used yet, so they always leave along the most beautiful walkway.)

This movement rule is deterministic: once a starting pond is fixed, the entire route is uniquely determined.

The students want to have lunch at the fine restaurant next to pond $P$. Each class becomes hungry after passing exactly $K$ walkways, and at that moment they must be standing at pond $P$. The value of $K$ may differ between classes.

Treating each of the $N$ ponds as a possible starting pond, determine how many distinct routes end at pond $P$ after using exactly $K$ walkways. Each starting pond produces exactly one route, so this equals the number of such starting ponds. A route may pass through pond $P$ earlier, but immediately after the $K$-th walkway it must be at $P$.

Answer this for $Q$ classes, that is, for $Q$ values of $K$.

The first line contains three integers $N$, $M$, and $P$ separated by spaces.

Each of the next $M$ lines describes one walkway: line $i$ (for $0 \le i < M$) contains the numbers of the two ponds joined by walkway $i$. The walkways are given in order of beauty, most beautiful first.

The next line contains the number of classes $Q$, and each of the following $Q$ lines contains one value of $K$.

For each class, print on its own line the number of distinct routes (starting ponds) that reach pond $P$ using exactly $K$ walkways, in the same order as the input. Print $0$ if no such route exists.