#P18947. [Mladen Manev 2021 A3] tours / 混合图中的往返路线

[Mladen Manev 2021 A3] tours / 混合图中的往返路线

混合图中的往返路线

一个混合图有 NN 个顶点、MM 条边。每条边是有向边或无向边,无自环,允许重边。

对于每个询问 (X,Y)(X,Y),判断是否能选取一条 X→YX\to Y 的路线和一条 Y→XY\to X 的路线,使这两条路线对每条无向边至多使用其中一个方向。路线可以重复经过边,但同一条无向边不能在本次往返中被双向使用。有向边只能按规定方向使用。

不同询问互相独立。等价地,每个询问分别判断:是否存在对所有无向边的某种定向,使 X,YX,Y 处于同一个强连通分量。

输入格式

第一行 N,MN,M。接下来 MM 行,每行 T,X,YT,X,Y;T=1T=1 表示无向边 X−YX-Y,T=2T=2 表示有向边 X→YX\to Y。

随后一行 QQ;接下来 QQ 行,每行两个不同顶点 X,YX,Y。

输出格式

一行连续的 QQ 个字符,每个字符为 1 或 0,分别表示对应询问可行或不可行。字符间不加空格。

数据范围

2≤N≤1052\le N\le10^5,1≤M,Q≤1061\le M,Q\le10^6,顶点编号为 11 至 NN。

示例

3 3
2 1 2
1 2 3
2 3 1
2
1 3
2 3
11

此处为整理者补充的简短示例。官方原始示例见附带 PDF。

来源与数据说明

2021 年 Dr. Mladen Manev,A3,原题名 tours。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。