โรงไฟฟ้า JOI มีฐาน $N$ ฐาน หมายเลข $1$ ถึง $N$ ฐานเหล่านี้เชื่อมต่อกันด้วยสายไฟ $N-1$ เส้น สายไฟเส้นที่ $i$ ($1 \le i \le N-1$) เชื่อมฐาน $A_i$ และฐาน $B_i$ ในทั้งสองทิศทาง เราสามารถเดินทางจากฐานใดก็ได้ไปยังฐานอื่นใดโดยผ่านสายไฟบางเส้น

แต่ละฐานของโรงไฟฟ้า JOI มีเครื่องกำเนิดไฟฟ้าได้ไม่เกินหนึ่งเครื่อง เครื่องกำเนิดไฟฟ้าแต่ละเครื่องมีสวิตช์ ในตอนเริ่มต้น สวิตช์ของเครื่องกำเนิดไฟฟ้าทุกเครื่องปิดอยู่ คุณเป็นผู้อำนวยการโรงไฟฟ้า JOI คุณสามารถเลือกเครื่องกำเนิดไฟฟ้าบางเครื่อง แล้วเปิดสวิตช์ของเครื่องที่เลือกทั้งหมดได้ (อนุญาตให้ไม่เลือกเครื่องใดเลย) เครื่องกำเนิดไฟฟ้ามีคุณสมบัติดังต่อไปนี้

• สมมติว่าฐาน $x,y,z$ มีเครื่องกำเนิดไฟฟ้า และสามารถเดินทางจากฐาน $x$ ไปยังฐาน $y$ แล้วจากฐาน $y$ ไปยังฐาน $z$ ตามลำดับ โดยไม่ผ่านสายไฟเส้นเดิมสองครั้ง หากสวิตช์ของเครื่องกำเนิดไฟฟ้าที่ฐาน $x$ และฐาน $z$ เปิดอยู่ เครื่องกำเนิดไฟฟ้าที่ฐาน $y$ จะเสีย
• เครื่องกำเนิดไฟฟ้าจะทำงานเมื่อสวิตช์ของมันเปิดอยู่และเครื่องไม่เสีย

สุดท้าย คุณจะได้รับรางวัลจากเครื่องกำเนิดไฟฟ้าที่ทำงาน โดยได้รับ 1 เยนต่อเครื่อง แต่คุณต้องจ่ายค่าซ่อมเครื่องกำเนิดไฟฟ้าที่เสียด้วย โดยจ่าย 1 เยนต่อเครื่อง เงินรางวัลรวมลบด้วยค่าซ่อมรวมคือกำไรของคุณ

จงเขียนโปรแกรมที่รับการจัดวางฐานและสายไฟ รวมถึงข้อมูลเครื่องกำเนิดไฟฟ้า แล้วคำนวณกำไรสูงสุดของคุณ

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

$$ \begin{array}{ll} N \\ A_1 & B_1 \\ \vdots \\ A_{N-1} & B_{N-1} \\ S \end{array} $$

ในที่นี้ $S$ เป็นสตริงยาว $N$ ที่แสดงเครื่องกำเนิดไฟฟ้าของฐานต่าง ๆ อักขระแต่ละตัวของ $S$ เป็น 0 หรือ 1 อักขระตัวที่ $i$ ($1 \le i \le N$) แสดงเครื่องกำเนิดไฟฟ้าของฐาน $i$ โดยเป็น 0 หากฐาน $i$ ไม่มีเครื่องกำเนิดไฟฟ้า และเป็น 1 หากฐาน $i$ มีเครื่องกำเนิดไฟฟ้า

ข้อมูลส่งออก

เขียนหนึ่งบรรทัดไปยังข้อมูลส่งออกมาตรฐาน โดยแสดงกำไรสูงสุดเมื่อคุณเลือกเครื่องกำเนิดไฟฟ้าบางเครื่องและเปิดสวิตช์ของเครื่องที่เลือกทั้งหมด

ข้อจำกัด

• $1 \le N \le 200\,000$
• $1 \le A_i \le N$ ($1 \le i \le N-1$)
• $1 \le B_i \le N$ ($1 \le i \le N-1$)
• $A_i \ne B_i$ ($1 \le i \le N-1$)
• สามารถเดินทางจากฐานใดก็ได้ไปยังฐานอื่นใดโดยผ่านสายไฟบางเส้น
• $S$ เป็นสตริงยาว $N$ ที่ประกอบด้วย 0 และ 1
• $S$ มี 1 อย่างน้อยหนึ่งตัว

งานย่อย

1. (6 คะแนน) $N \le 16$
2. (41 คะแนน) $N \le 2\,000$
3. (53 คะแนน) ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

6
2 3
4 3
1 3
3 5
6 2
110011

ข้อมูลส่งออก 1

3

หมายเหตุ

ในตัวอย่างนี้ ฐาน $1,2,5,6$ มีเครื่องกำเนิดไฟฟ้า

หากคุณเปิดสวิตช์ที่ฐาน $1,2,5$ เครื่องกำเนิดไฟฟ้าที่ฐาน $1,2,5$ จะทำงาน และคุณจะได้รับ 3 เยน เนื่องจากไม่ต้องจ่ายค่าซ่อม กำไรจึงเป็น 3 เยน นี่คือกำไรสูงสุด จึงแสดงผล 3

ในทางกลับกัน หากคุณเปิดสวิตช์ที่ฐาน $1,5,6$ เครื่องกำเนิดไฟฟ้าที่ฐาน $2$ จะเสีย และเครื่องกำเนิดไฟฟ้าที่ฐาน $1,5,6$ จะทำงาน คุณจะได้รับ 3 เยน และจ่ายค่าซ่อม 1 เยน ดังนั้นกำไรของคุณจะเป็น 2 เยน

หากคุณเปิดสวิตช์ที่ฐาน $1,2,5,6$ เครื่องกำเนิดไฟฟ้าที่ฐาน $2$ จะเสีย และเครื่องกำเนิดไฟฟ้าที่ฐาน $1,5,6$ จะทำงาน คุณจะได้รับ 3 เยน และจ่ายค่าซ่อม 1 เยน ดังนั้นกำไรของคุณจะเป็น 2 เยน

ข้อมูลนำเข้า 2

8
1 2
3 5
6 4
4 5
5 2
7 2
2 8
11111111

ข้อมูลส่งออก 2

3

ข้อมูลนำเข้า 3

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

ข้อมูลส่งออก 3

5