小希的迷宫

  1/**
  2 *    author: Akvicor
  3 *    created: 2019-06-13 17-17-53
  4**/
  5
  6#include <bits/stdc++.h>
  7
  8using namespace std;
  9
 10#ifdef DEBUG
 11string to_string(string s) {
 12	return '"' + s + '"';
 13}
 14
 15string to_string(const char* s) {
 16	return to_string((string) s);
 17}
 18
 19string to_string(bool b) {
 20return (b ? "true" : "false");
 21}
 22
 23template <typename A, typename B>
 24string to_string(pair<A, B> p) {
 25	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
 26}
 27
 28template <typename A>
 29string to_string(A v) {
 30	bool first = true;
 31	string res = "{";
 32	for (const auto &x : v) {
 33		if (!first) {
 34			res += ", ";
 35		}
 36		first = false;
 37		res += to_string(x);
 38	}
 39	res += "}";
 40	return res;
 41}
 42
 43void debug_out() { cerr << endl; }
 44
 45template <typename Head, typename... Tail>
 46void debug_out(Head H, Tail... T) {
 47	cerr << " " << to_string(H);
 48	debug_out(T...);
 49}
 50#endif
 51
 52#ifdef DEBUG
 53#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
 54#else
 55#define debug(...) 17
 56#endif
 57
 58#ifdef DEBUG
 59#define FAST_IO 17
 60#define cout cout << "-->"
 61#else
 62#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 63#define endl '\n'
 64#endif
 65
 66#define LL long long
 67#define ULL unsigned long long
 68#define rep(i, n) for(int i = 0; i < (n); ++i)
 69#define reep(i, n) for(int i = 0; i <= (n); ++i)
 70#define lop(i, a, n) for(int i = a; i < (n); ++i)
 71#define loop(i, a, n) for(int i = a; i <= (n); ++i)
 72#define ALL(v) (v).begin(), (v).end()
 73#define PB push_back
 74#define VI vector<int>
 75#define PII pair<int,int>
 76#define FI first
 77#define SE second
 78#define SZ(x) ((int)(x).size())
 79
 80const double EPS = 1e-6;
 81const double PI = acos(-1.0);
 82const int INF = 0x3f3f3f3f;
 83const LL LINF = 0x7f7f7f7f7f7f7f7f;
 84const int MAXN = (int)1e6 + 10;
 85const int MOD = (int)1e9 + 7;
 86
 87class UnionFind{
 88	private:
 89		int * parent;
 90		int * rank;
 91		bool * ral;
 92		int count;
 93	public:
 94		UnionFind(int n){
 95			parent = new int[n];
 96			rank = new int[n];
 97			ral = new bool[n];
 98			this->count = n;
 99			for(int i = 0; i < n; ++i){
100				parent[i] = i;
101				rank[i] = 1;
102				ral[i] = false;
103			}
104		}
105		~UnionFind(){
106			delete[] parent;
107			delete[] rank;
108		}
109
110		int find(int p){
111			while(p != parent[p]){
112				p = parent[p];
113			}
114			return p;
115		}
116
117		bool isConnected(int p, int q){
118			this->ral[p] = true;
119			this->ral[q] = true;
120			return find(p) == find(q);
121		}
122
123		bool is_one_grap(){
124			int res = 0;
125			for(int i = 0; i <= this->count; ++i){
126				if(this->parent[i] == i && this->ral[i]) ++res;
127			}
128			return res <= 1;
129		}
130
131		void unionElements(int p, int q){
132			int pRoot = find(p);
133			int qRoot = find(q);
134
135			if(pRoot == qRoot) return;
136
137			if(rank[pRoot] < rank[qRoot]){
138				parent[pRoot] = qRoot;
139			}else if(rank[qRoot] < rank[pRoot]){
140				parent[qRoot] = pRoot;
141			}else{
142				parent[pRoot] = qRoot;
143				rank[qRoot] += 1;
144			}
145		}
146
147		int cnt(){
148			int cnt = 0;
149			for(int i = 0; i < this->count; ++i){
150				if(parent[i] == i) ++cnt;
151			}
152			return cnt;
153		}
154};
155
156int main(){
157	FAST_IO;
158
159	int p, q;
160	
161	while(true){
162		bool flag = true;
163		UnionFind uf = UnionFind(100010);
164		while(cin >> p >> q){
165			if(p == 0 && q == 0) break;
166			if(p == -1 && q == -1) return 0;
167			if(!flag) continue;
168			if(uf.isConnected(p, q)) flag = false;
169			else uf.unionElements(p, q);
170		}
171		if(flag && uf.is_one_grap()) cout << "Yes" << endl;
172		else cout << "No" << endl;
173	}
174
175	return 0;
176}