Start: Aug, 31, 2026 14:00:00
AI-prompt作业
End: Jan, 07, 2027 23:59:00
Time elapsed:
Time remaining:

小王子 3434

Time Limit:  1 s      Memory Limit:   256 MB
Submission:4     AC:3     Score:10

Description

“如果我沿着这条路一直往上面去,我就可以摘到那一颗星星。”

“可是物理好难啊。”

“那我还是去炸星星好了。”

“就算是要到月亮上去罚站也没关系呀。”

十二月的风凌冽。

他站在阳台上,嘴里叼着一根从隔壁房间偷来的草莓味棒棒糖,眯着眼试图从漫天飞雪中嗅到一丝秋天的气息。黑 与白构成不分明的界限,混沌地勾勒出陌生的形状。

倒像是一堆散乱的线条。

他又眯着眼看那清凌凌的夜空。

像是那么多的星星。

随手把剩下的棍子扔向,他打了个哈欠,想起厨房里的《赢在微点》。

再看,是N颗星星牵着N-1条线。

是N-1条白色的线束缚着N颗星星。

“你为什么盯着星星看这么久?”

“我喜欢一颗小星星,所以遥望星空,试图用大脑向宇宙发送一些信号。”

“那宇宙给你反馈了吗?”

“没呢。”

“希望那颗小星星可以在宇宙来临之前,先跑到我面前哦。”
“那就换一颗嘛,天上的星星多得是。”

——可那线条好少。

——那便多一点好了。

于是他依稀看见M条黑色的线与N条白色的线交错,不重合也不缠绕。都只是轻轻地拉着那些星星,并不捆绑,连接 着两颗不同的星星,却不知怎的令他们无法脱身。

“宇宙给你反馈了吗?”

“没有。”

“那就换一颗嘛,天上的星星多得是。”

“环游整个星系,我大概找不到更亮的星星。”

——那就去摘啊。自己的星星自己摘。

——可是我的宇宙飞船可能会遇到流星,可能会用光所有的燃料。
——可是宇宙里的信号表示,那颗小星星在靠近。星河万顷,都是见面礼。

——可他有点慢啊。

——那就把他炸下来。

他看着那些不存在的线条与星星,决定用他仅有的两发导弹之中的一发去毁灭一条白线,使那些星星分成两部分。

想着他在物理书上写下:“#define 炸星星 使那些星星分成两部分”。

然后失望地发现有些时候无法成功地炸星星。

于是他决定用仅剩的一发他本决定用来保证晚年幸福的导弹去毁灭一条黑线。

不是每一个月亮都能遇到宇航员的。

但他还是想知道他有多少种使他的小星星在下一秒便出现在他怀里的方案。

可他要送什么见面礼给他的小星星呢?

他只有两发导弹、一本《赢在微点》、一本《普通高中课程标准实验教科书物理必修1》和一根草莓味棒棒糖。

草莓味棒棒糖已经被他吃完并丢弃了,而星星想必也不会喜欢物理书与物理教辅。

所以他决定就算一发导弹一条白线就能把他的小星星带到他面前,他也要再炸一条黑线给他的小星星。

也许这样会让他的爱与企盼再长大一点点吧。

至少看起来长大一点点。

顺便,把方案数也送给他的小星星。

星星被分成了两部分,那么下面的星星会下坠吧。

如果他们没有遇见像他一样的人,也许他们会遇见饥饿的小怪兽,小怪兽也许会嚼碎这些小星球。

“我就藏在漫天的星光里呀。”

他不怕外星人把他那颗星星抢走的。

抢不走的。

对于一张图 G = {V ,E} ,其中 E1 ∩ E2 = ∅,E1 ∪ E2 = E ,且图 G = {V ,E1} 为一棵树,你需要选出 两条边 e1 ∈ E1, e2 ∈ E2 ,使得图 G = {V ,∁E{e1, e2}} 不连通,求能选出的集合 {e1, e2} 数量。

Input

第一行包含两个整数N和M;
之后N-1行,每行包括两个整数X和Y,表示X和Y之间有一条白线; 之后M行,每行包括两个整数X和Y,表示X和Y之间有一条黑线。

Output

输出一个整数表示方案数。

Samples

input
4 1 1 2 2 3 1 4 3 4
output
3

Hint

数据范围

对于20%的数据,1≤N,M≤100;
对于100%的数据,1≤N,M≤2×10^5。