CF1391E-Pairs of Pairs

题目:

题目描述:

You have a simple and connected undirected graph consisting of $ n $ nodes and $ m $ edges.

Consider any way to pair some subset of these $ n $ nodes such that no node is present in more than one pair.

This pairing is valid if for every pair of pairs, the induced subgraph containing all $ 4 $ nodes, two from each pair, has at most $ 2 $ edges (out of the $ 6 $ possible edges). More formally, for any two pairs, $ (a,b) $ and $ (c,d) $ , the induced subgraph with nodes $ {a,b,c,d} $ should have at most $ 2 $ edges.

Please note that the subgraph induced by a set of nodes contains nodes only from this set and edges which have both of its end points in this set.

Now, do one of the following:

• Find a simple path consisting of at least $ \lceil \frac{n}{2} \rceil $ nodes. Here, a path is called simple if it does not visit any node multiple times.
• Find a valid pairing in which at least $ \lceil \frac{n}{2} \rceil $ nodes are paired.

It can be shown that it is possible to find at least one of the two in every graph satisfying constraints from the statement.

输入格式:

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). Description of the test cases follows.

The first line of each test case contains $ 2 $ integers $ n, m $ ( $ 2 \le n \le 5\cdot 10^5 $ , $ 1 \le m \le 10^6 $ ), denoting the number of nodes and edges, respectively.

The next $ m $ lines each contain $ 2 $ integers $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \neq v $ ), denoting that there is an undirected edge between nodes $ u $ and $ v $ in the given graph.

It is guaranteed that the given graph is connected, and simple — it does not contain multiple edges between the same pair of nodes, nor does it have any self-loops.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 5\cdot 10^5 $ .

It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^6 $ .

输出格式:

For each test case, the output format is as follows.

If you have found a pairing, in the first line output “PAIRING” (without quotes).

• Then, output $ k $ ( $ \lceil \frac{n}{2} \rceil \le 2\cdot k \le n $ ), the number of pairs in your pairing.
• Then, in each of the next $ k $ lines, output $ 2 $ integers $ a $ and $ b $ — denoting that $ a $ and $ b $ are paired with each other. Note that the graph does not have to have an edge between $ a $ and $ b $ !
• This pairing has to be valid, and every node has to be a part of at most $ 1 $ pair.

Otherwise, in the first line output “PATH” (without quotes).

• Then, output $ k $ ( $ \lceil \frac{n}{2} \rceil \le k \le n $ ), the number of nodes in your path.
• Then, in the second line, output $ k $ integers, $ v_1, v_2, \ldots, v_k $ , in the order in which they appear on the path. Formally, $ v_i $ and $ v_{i+1} $ should have an edge between them for every $ i $ ( $ 1 \le i < k $ ).
• This path has to be simple, meaning no node should appear more than once.

样例:

样例输入 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

4
6 5
1 4
2 5
3 6
1 5
3 5
6 5
1 4
2 5
3 6
1 5
3 5
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3
12 14
1 2
2 3
3 4
4 1
1 5
1 12
2 6
2 7
3 8
3 9
4 10
4 11
2 4
1 3

样例输出 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

PATH
4
1 5 3 6
PAIRING
2
1 6
2 4
PAIRING
3
1 8
2 5
4 10
PAIRING
4
1 7
2 9
3 11
4 5

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include "ybwhead/ios.h"
const int maxm = 1e6 + 10, maxn = 5e5 + 10;
struct edge
{
    int v, nxt;
} e[maxm << 1];
int head[maxn], tot;
void __ADD(int u, int v)
{
    e[++tot].v = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}
void add(int u, int v)
{
    __ADD(u, v);
    __ADD(v, u);
}
int n, m;
int maxh;
int dep[maxn];
int vis[maxn];
int dfn[maxn];
int f[maxn];
int num;
vector<int> dd[maxn];
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    if (dep[u] > dep[maxh])
        maxh = u;
    vis[u] = ++num;
    dd[dep[u]].push_back(u);
    f[u] = fa;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (vis[v])
            continue;
        dfs(v, u);
    }
}
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        yin >> n >> m;
        for (int i = 1; i <= n; i++)
            head[i] = vis[i] = 0;
        tot = 0;
        for (int i = 1; i <= m; i++)
        {
            int u, v;
            yin >> u >> v;
            add(u, v);
        }
        maxh = num = 0;
        for (int i = 1; i <= n; i++)
            dd[i].clear();
        dfs(1, 0);
        if (dep[maxh] >= (n + 1) / 2)
        {
            yout << "PATH" << endl;
            yout << dep[maxh] << endl;
            while (maxh)
                yout << maxh << " ", maxh = f[maxh];
            yout << endl;
            continue;
        }
        maxh = (n + 1) >> 1;
        maxh = (maxh + 1) >> 1;
        yout << "PAIRING" << endl;
        yout << maxh << endl;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j + 1 < dd[i].size(); j += 2)
            {
                yout << dd[i][j] << " " << dd[i][j + 1] << endl;
                --maxh;
                if (!maxh)
                    break;
            }
            if (!maxh)
                break;
        }
    }
    return 0;
}