壯遊

發布時間: June 27, 2024, 7:50 p.m.   最後更新時間: June 28, 2024, 7:48 a.m.   時間限制: 3000ms   記憶體限制: 128M

壯遊(英語:Grand Tour)是指自文藝復興時期以後,歐洲貴族子弟的傳統旅行,後來也擴展到中歐、義大利、西班牙之富有中產階層。壯遊尤其盛行於18世紀之英國,留下了豐富的文字記述。「Grand Tour」譯為「壯遊」一詞,典故則來自杜甫的《壯遊》一詩:

「往昔十四五,出遊翰墨場。斯文崔魏徒,以我似班揚。

七齡思即壯,開口詠鳳凰。九齡書大字,有作成一囊。

性豪業嗜酒,嫉惡懷剛腸。脱略小時輩,結交皆老蒼。

飲酣視八極,俗物都茫茫。東下姑蘇台,已具浮海航。

到今有遺恨,不得窮扶桑。王謝風流遠,闔閭丘墓荒。

劍池石壁仄,長洲荷芰香。嵯峨閶門北,清廟映回塘。

每趨吳太伯,撫事淚浪浪。枕戈憶勾踐,渡浙想秦皇。

蒸魚聞匕首,除道哂要章。越女天下白,鏡湖五月涼。

剡溪藴秀異,欲罷不能忘。歸帆拂天姥,中歲貢舊鄉。

氣劘屈賈壘,目短曹劉牆。忤下考功第,獨辭京尹堂。

放蕩齊趙間,裘馬頗清狂。春歌叢台上,冬獵青丘旁。

呼鷹皂櫪林,逐獸雲雪岡。射飛曾縱鞚,引臂落鶖鶬。

蘇侯據鞍喜,忽如攜葛強。快意八九年,西歸到咸陽。

許與必詞伯,賞遊實賢王。曳裾置醴地,奏賦入明光。

天子廢食召,羣公會軒裳。脱身無所愛,痛飲信行藏。

黑貂不免敝,斑鬢兀稱觴。杜曲晚耆舊,四郊多白楊。

坐深鄉黨敬,日覺死生忙。朱門任傾奪,赤族迭罹殃。

國馬竭粟豆,官雞輸稻粱。舉隅見煩費,引古惜興亡。

河朔風塵起,岷山行幸長。兩宮各警蹕,萬里遙相望。

崆峒殺氣黑,少海旌旗黃。禹功亦命子,涿鹿親戎行。

翠華擁英嶽,螭虎啖豺狼。爪牙一不中,胡兵更陸梁。

大軍載草草,凋瘵滿膏肓。備員竊補袞,憂憤心飛揚。

上感九廟焚,下憫萬民瘡。斯時伏青蒲,廷爭守禦牀。

君辱敢愛死,赫怒幸無傷。聖哲體仁恕,宇縣復小康。

哭廟灰燼中,鼻酸朝未央。小臣議論絕,老病客殊方。

鬱郁苦不展,羽翮困低昂。秋風動哀壑,碧蕙捐微芳。

之推避賞從,漁父濯滄浪。榮華敵勳業,歲暮有嚴霜。

吾觀鴟夷子,才格出尋常。羣凶逆未定,側佇英俊翔。」

《紐約時報》如此描述壯遊:

「三百年前,接受過牛橋教育的富有英國年輕人開始前往法國和義大利各地跋涉,尋求藝術、文化和西方文明的根源。憑藉幾乎無限的資金,貴族接連數月或數年漫遊各地,他們訂購繪畫,完善自己的語言技能,與歐洲大陸上流社會交往。」

壯遊的主要價值,據信一方面是接觸古代和文藝復興時期的文化遺產,一方面是接觸歐洲大陸的貴族和上流社會。此外在當時,此乃觀看某些藝術品以及聽到某些音樂的唯一途徑。一次壯遊可能會持續幾個月到幾年,通常有博學的嚮導或導師陪伴。壯遊超出了表面上的文化意義,正如愛德華·帕爾默·湯普森指出,「18世紀統治階級的控制主要體現在文化霸權,其次才表達為經濟實力或體力(軍事實力)。」

某天Colin也想效法古代歐洲學子的壯遊。已知某國家有$n$個城市,編號$1$~$n$,以及$m$條道路,他希望能走遍此國家的所有城市與道路,但他有個小小執著,希望在壯遊的途中,相同的城市可以重複經過,但同樣的道路不可以再次走過,請問此國家是否能滿足Colin的要求?

第一行輸入兩正整數$n,m$,分別表示某國家的城市與道路數量
接下來$m$行分別輸入每條道路連接的兩個城市$a,b$(兩城市間可能有不只一條道路連接)
$2\le n\le 10^6$
$1\le m\le 10^6$

若此國家符合Colin的要求,輸出"Yes",否則輸出"No"

複製範例
5 6
1 2
1 5
2 3
2 5
3 4
4 5
Yes
複製範例
6 8
1 2
1 6
2 3
2 6
3 4
3 5
4 5
5 6
No

提示一:

數學家歐拉在1736年發表的論文《柯尼斯堡的七橋》中提出了一筆畫定理:

「連通的無向圖$G$存在歐拉路徑(能夠遍歷完所有的邊而沒有重複)的充要條件是:$G$中奇頂點(連接的邊數量為奇數的頂點)的數目等於$0$或者$2$。且如果奇頂點的數目等於$2$時,必須正好分別為起點和終點。」

提示二:

輸入測資可能很大,可以在main函式中加入cin/cout的輸入輸出優化指令

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

或是使用scanf/printf

array

竹中軟研39th競賽組期末競賽