A - 高橋王国と青木王国

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

AtCoder 王国には N 個の街があります。N 個の街には 1 から N までの番号がついており、街 1 に高橋君が、街 N に青木君が住んでいます。

街の間は M 本の道路で結ばれています。各道路は一方通行ですが、複数本の道路が 2 つの街の間に存在することもあります。特に、順向きと逆向きの道路が 1 本ずつ存在することにより双方向に移動可能な場合もあります。

AtCoder 王国は高橋王国と青木王国の 2 つの国に分断されるという噂が流れています。分断は以下を満たすように行われるそうです。

  • N 個の街のうちの一部が高橋王国に、残りが青木王国になります。
  • 高橋王国には街 1 が、青木王国には街 N が必ず含まれます。
  • 高橋王国から青木王国への道路は全て撤去されます。すなわち、始点が高橋王国に、終点が青木王国に所属するような道路が全て撤去されます。
  • 撤去する道路の本数が最小になるように分割を行います。

これらを満たす分割の方法は、必ずしも一意ではありません。従って、国民の多くは、国がどのように分断されるかについて心配しています。

そこで、あなたの仕事は、国民からの質問に回答するプログラムを作成することです。2 つの街が質問として与えられるので、それぞれの質問について、「それらが同じ国に所属することになる可能性はあるか」と「それらは違う国に所属することになる可能性はあるか」を回答するプログラムを作成して下さい。

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1
a_2 b_2
:
a_M b_M
Q
c_1 d_1
c_2 d_2
:
c_Q d_Q
  • 1 行目には、街の個数 N (1 ≦ N ≦ 5,000) と道の本数 M (1 ≦ M ≦ 50,000) が与えられる。
  • 2 行目からの M 行のうち i 行目には、i 番目の道を表す整数 a_i,b_i (1≦a_i, b_i≦N, a_i ≠ b_i) が空白区切りで与えられる。これは、道 i が街 a_i を出発し街 b_i へ到達するものであることを表す。
  • M+1 行目には、国民からの質問の個数を表す整数 Q (1≦Q≦100,000) が与えられる。
  • M+2 行目からの Q 行のうち、j 行目には、j 番目の質問を表す整数 c_j, d_j (1 ≦ c_j, d_j ≦ N, c_j ≠ d_j) が与えられる。これは、j 番目の質問が街 c_j と街 d_j に関するものであることを表す。

出力

Q 個の質問について、回答を 1 行ずつ出力せよ。 質問 j への回答は 2 つの語からなり、空白で区切って出力すること。

  • 1 つめの語は、街 c_j と街 d_j が同じ国に所属することになる可能性はあるかを表す。同じ国に所属する可能性がある場合 YES、無い場合 NO と出力せよ。
  • 2 つめの語は、街 c_j と街 d_j が違う国に所属することになる可能性はあるかを表す。違う国に所属する可能性がある場合 YES、無い場合 NO と出力せよ。

出力の末尾には改行を入れること。

部分点

この問題には部分点が設定されている。

  • N ≦ 100, M ≦ 1,000, Q ≦ 100 を満たすデータセットに正解した場合は、20 点が与えられる。
  • 追加の制約のないデータセットに正解した場合は、上記とは別に 80 点が与えられる。

入力例1

3 5
1 2
1 2
1 2
2 3
2 3
3
1 2
2 3
1 3

出力例1

YES NO
NO YES
NO YES

複数本の道路が 2 つの街の間に存在することもあることに注意して下さい。

入力例2

3 5
3 2
3 2
3 2
2 1
2 1
3
1 2
2 3
1 3

出力例2

YES YES
YES YES
NO YES

高橋王国から青木王国への道路のみ撤去されることに気をつけて下さい。

入力例3

8 10
1 2
1 3
1 4
2 3
3 5
4 6
5 8
6 7
6 8
7 8
7
1 2
2 3
2 6
3 6
4 5
5 6
6 7

出力例3

YES NO
YES NO
NO YES
NO YES
YES YES
YES YES
YES NO
B - TRAX

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

すぬけ君はTRAXというボードゲームのコマを並べて遊んでいます。TRAXのコマは下図のようなものです。

token

すぬけ君はこのコマを以下のようなルールで並べようとしています。

  • H*W 個のコマを 全て表向きで 、縦 H 行、横 W 行のマス目状に敷き詰める。コマの向きは 4 通り考えられるがいずれの向きでも構わない。
  • 赤い線は隣のコマの赤い線と、白い線は隣のコマの白い線と繋がるようにしなければならない。つまり、赤い線の端と白い線の端が隣り合ってはいけない。
  • 輪っかができてはならない。下図は輪っかの例である。右の例の白い線のような大きな輪っかもできてはいけません。
cycle

すぬけ君はすでに N 個のコマを置きました。i (1 ≦ i ≦ N) 個目のコマは R_i 行目の C_i 列目に D_i の向きで置きました。向きは 1 ～ 4 の整数で表され、それぞれの向きは下図のように対応しています。

direction

さて、残りのコマの置き方は何通りあるでしょうか？答えは非常に大きな数になることがあるので 10^9+7 で割った余りを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

H W
N
R_1 C_1 D_1
R_2 C_2 D_2
:
R_N C_N D_N
  • 1 行目には、2 つの整数 H (1 ≦ H ≦ 10^5), W (1 ≦ W ≦ 10^5) が空白区切りで与えられる。これは、すぬけ君がコマを縦 H 行、横 W 行のマス目状に敷き詰めようとしていることを表す。
  • 2 行目には、すぬけ君がすでに置いたコマの個数を表す整数 N (0 ≦ N ≦ 10^5) が与えられる。
  • 3 行目からの N 行には、すぬけ君がすでに置いたコマの情報が与えられる。このうち i (1 ≦ i ≦ N) 行目には 3 つの整数 R_i (1 ≦ R_i ≦ H), C_i (1 ≦ C_i ≦ W), D_i (1 ≦ D_i ≦ 4) が空白区切りで与えられる。これは、すぬけ君が R_i 行目の C_i 列目に D_i の向きでコマを置いたことを表している。ただし、同じ場所は 2 回以上与えられない、すなわち p \neq q のとき R_p \neq R_q または C_p \neq C_q を満たすことが保証される。

部分点

この問題には部分点が設定されている。

  • N = 0 を満たすデータセットに正解した場合は、90 点が与えられる。
  • 追加の制約のないデータセットに正解した場合は、上記とは別に 60 点が与えられる。

出力

残りのコマの置き方の個数を 10^9+7 (1,000,000,007) で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

2 2
1
1 1 4

出力例1

4

下図のような 4 通りの置き方が考えられます。

sample

入力例2

2 10
2
1 1 1
1 2 1

出力例2

0

どのように置いてもルールを満たすような置き方はできません。

入力例3

2015 1114
0

出力例3

711460824

入力例4

2 2
2
1 1 1
2 2 3

出力例4

0

入力例5

5 6
3
1 2 2
4 1 1
5 6 4

出力例5

12

入力例6

5 6
2
3 3 4
3 4 2

出力例6

39