Binary Search Tree Typo

You are given a binary tree root which is almost a binary search tree except two nodes’ values have been swapped. Return the original binary search tree.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Binary-Search-Tree-Typo

Examples

Example 1

Input

• root =

Output

• answer =

Explanation

We can swap 1 and 5.

Example 2

Input

• root =

Output

• answer =

Explanation

We can swap 0 and 1.

Solution