트리와 쿼리 20

시간 제한

5초

메모리 제한

512 MB

문제

$N$ \uAC1C\uC758 \uC815\uC810\uC73C\uB85C \uC774\uB8E8\uC5B4\uC9C4 \uD3EC\uB808\uC2A4\uD2B8\uAC00 \uC788\uB2E4. \uC815\uC810\uC740 $1$ \uBD80\uD130 $N$ \uAE4C\uC9C0 \uBC88\uD638\uAC00 \uB9E4\uACA8\uC838 \uC788\uACE0, \uCC98\uC74C\uC5D0\uB294 \uAC04\uC120\uC774 \uC5C6\uB2E4. \uAC01 \uC815\uC810 $v$ \uC5D0\uB294 \uC815\uC218 $X_v$ \uAC00 \uC788\uC73C\uBA70, \uCD08\uAE30\uAC12\uC740 \uBAA8\uB450 $1$ \uC774\uB2E4.

\uB2E4\uC74C \uCFFC\uB9AC\uB97C \uCC98\uB9AC\uD558\uB294 \uD504\uB85C\uADF8\uB7A8\uC744 \uC791\uC131\uD558\uC2DC\uC624.

1 a b c: \uC815\uC810 $a$ \uC640 \uC815\uC810 $b$ \uB97C \uAC00\uC911\uCE58 $c$ \uC778 \uAC04\uC120\uC73C\uB85C \uC5F0\uACB0\uD55C\uB2E4. \uC774 \uCFFC\uB9AC\uB294 \uC218\uD589\uD55C \uB4A4\uC5D0\uB3C4 \uC804\uCCB4 \uADF8\uB798\uD504\uAC00 \uD3EC\uB808\uC2A4\uD2B8\uC778 \uACBD\uC6B0\uC5D0\uB9CC \uC8FC\uC5B4\uC9C4\uB2E4.
2 a b: \uC815\uC810 $a$ \uC640 \uC815\uC810 $b$ \uB97C \uC787\uB294 \uAC04\uC120\uC744 \uC81C\uAC70\uD55C\uB2E4. \uC774 \uCFFC\uB9AC\uB294 \uB450 \uC815\uC810 \uC0AC\uC774\uC5D0 \uAC04\uC120\uC774 \uC788\uC744 \uB54C\uB9CC \uC8FC\uC5B4\uC9C4\uB2E4.
3 a: \uBA3C\uC800 $X_a$ \uB97C $1-X_a$ \uB85C \uBC14\uAFBC\uB2E4. \uADF8 \uB2E4\uC74C \uC815\uC810 $a$ \uAC00 \uC18D\uD55C \uD2B8\uB9AC\uC758 \uC815\uC810\uC744 $v_1, v_2, \dots, v_k$ \uB77C\uACE0 \uD560 \uB54C, \uC544\uB798 \uAC12\uC758 \uCD5C\uC19F\uAC12\uC744 \uCD9C\uB825\uD55C\uB2E4.

\min_{1 \le i \le k}\left\{ \sum_{1 \le j \le k} dist(v_i, v_j) \times X_{v_j} \right\}

\uC5EC\uAE30\uC11C $dist(v_i, v_j)$ \uB294 $v_i$ \uC5D0\uC11C $v_j$ \uB85C \uAC00\uB294 \uACBD\uB85C\uC5D0 \uC788\uB294 \uBAA8\uB4E0 \uAC04\uC120 \uAC00\uC911\uCE58\uC758 \uD569\uC774\uB2E4.

입력

\uCCAB\uC9F8 \uC904\uC5D0 \uC815\uC810\uC758 \uAC1C\uC218 $N$ \uACFC \uCFFC\uB9AC\uC758 \uAC1C\uC218 $Q$ \uAC00 \uC8FC\uC5B4\uC9C4\uB2E4. \uB458\uC9F8 \uC904\uBD80\uD130 $Q$ \uAC1C\uC758 \uC904\uC5D0 \uCFFC\uB9AC\uAC00 \uD55C \uC904\uC5D0 \uD558\uB098\uC529 \uC8FC\uC5B4\uC9C4\uB2E4.

\uCFFC\uB9AC\uC5D0 \uB4F1\uC7A5\uD558\uB294 \uC815\uC810 \uBC88\uD638\uB294 \uC554\uD638\uD654\uB418\uC5B4 \uC788\uC73C\uBBC0\uB85C, \uCFFC\uB9AC\uB97C \uC218\uD589\uD558\uAE30 \uC804\uC5D0 \uD574\uB3C5\uD574\uC57C \uD55C\uB2E4. \uC785\uB825\uC73C\uB85C \uC8FC\uC5B4\uC9C4 \uC815\uC810 \uBC88\uD638\uAC00 $x$ \uC774\uACE0 \uC9C0\uAE08\uAE4C\uC9C0 \uCC98\uB9AC\uD55C \uBAA8\uB4E0 $3$ \uBC88 \uCFFC\uB9AC\uC758 \uCD9C\uB825\uAC12 \uD569\uC774 $S$ \uB77C\uBA74, \uC2E4\uC81C \uC815\uC810 \uBC88\uD638\uB294 \uB2E4\uC74C\uACFC \uAC19\uB2E4.

(x - 1 + S) \bmod N + 1

\uCCAB \uBC88\uC9F8 $3$ \uBC88 \uCFFC\uB9AC \uC804\uC5D0\uB294 $S=0$ \uC73C\uB85C \uB454\uB2E4. $1$ \uBC88 \uCFFC\uB9AC\uC758 \uAC00\uC911\uCE58 $c$ \uB294 \uC554\uD638\uD654\uB418\uC9C0 \uC54A\uB294\uB2E4.

출력

$3$ \uBC88 \uCFFC\uB9AC\uC5D0\uC11C \uAD6C\uD55C \uAC12\uC744 \uCFFC\uB9AC\uAC00 \uC8FC\uC5B4\uC9C4 \uC21C\uC11C\uB300\uB85C \uD55C \uC904\uC5D0 \uD558\uB098\uC529 \uCD9C\uB825\uD55C\uB2E4.

제한

$1 \le N \le 10^5$
$1 \le Q \le 3 \times 10^5$
$1 \le a, b \le N$
$a \ne b$
$1 \le c \le 10^8$