Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <string>
- #include <utility>
- #include <algorithm>
- #include <cmath>
- #include <map>
- #include <set>
- #include <queue>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair<int,int> pii;
- #define pb push_back
- #define mp make_pair
- #define sz(a) int((a).size())
- #define forn(i, n) for (int i=0; i<(n); ++i)
- const int maxn = 256;
- vector<int> g[maxn];
- bool v1[maxn], v2[maxn];
- int mt[maxn], root;
- int p[maxn];
- int bmt[maxn];
- int n;
- bool dfs(int x)
- {
- if (v1[x]) return false;
- v1[x] = v2[x] = true;
- forn (i, sz(g[x]))
- {
- int y = g[x][i];
- if (y != root)
- if (mt[y] == -1 || (!v2[y] && dfs(mt[y])))
- {
- mt[x] = y;
- mt[y] = x;
- return true;
- }
- }
- v2[x] = false;
- return false;
- }
- int matching()
- {
- forn (i, n) mt[i] = -1;
- int res = 0;
- forn (i, n) if (mt[p[i]] == -1)
- {
- forn (j, n) v1[j] = v2[j] = false;
- root = p[i];
- if (dfs(p[i])) ++res;
- }
- return res;
- }
- bool solve()
- {
- if (n % 2 != 0) return false;
- forn (i, n) p[i] = i;
- int ok = 0, m, f = 0;
- forn (it, 10)
- {
- m = matching();
- if (m == n/2)
- {
- if (!f)
- {
- f = 1;
- forn (i, n) bmt[i] = mt[i];
- }
- int same = 1;
- forn (i, n) if (bmt[i] != mt[i]) same = 0;
- if (!same) return false;
- ok = 1;
- }
- random_shuffle(p, p+n);
- }
- if (!ok) return false;
- //forn (i, n) printf("%d ", mt[i]); puts("");
- return true;
- }
- int main()
- {
- freopen("a.in", "r", stdin);
- int tc; scanf("%d", &tc);
- while (tc--)
- {
- scanf("%d", &n);
- forn (i, n)
- {
- int m; scanf("%d", &m);
- g[i].clear();
- forn (j, m)
- {
- int x; scanf("%d", &x);
- g[i].pb(x-1);
- }
- }
- if (solve()) puts("YES"); else puts("NO");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment